#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ID_LEN 20 
#define NAME_LEN 50  
#define MAX_STU 100  

// 各学生顶点对应的邻接链表中的结点
typedef struct Edge{
    int idx;  
    struct Edge *next;  
}Edge;

// 邻接表中各学生顶点
typedef struct{
    char id[ID_LEN];
    char name[NAME_LEN];
    float score;
    Edge *link;  
    int visited;  //       
}Student;

// 邻接表
typedef struct{
    Student stu[MAX_STU];  
    int stu_num;  
    int link_num; 
}Graph;

// 初始化系统(图)
void InitGraph(Graph *g){
    int i;
    g->stu_num=0;  
    g->link_num=0;  
    for(i=0;i<MAX_STU;i++){
        g->stu[i].link=NULL;
        g->stu[i].visited=0;  //
    }
} 

// 添加学生(顶点)
void AddStu(Graph *g,char *id,char *name,float score) {
    if(g->stu_num>=MAX_STU){
        printf("学生满了无法再添加!\n");
        return ;
    }
     strcpy(g->stu[g->stu_num].id,id);
     strcpy(g->stu[g->stu_num].name,name);
     g->stu[g->stu_num].score=score;
     g->stu_num++;
     printf("添加学生%s成功!\n",id);
}

// 定位某学生下标()
int FindStuIdx(Graph *g,char *id){
    for(int i=0;i<g->stu_num;i++){
        if(strcmp(g->stu[i].id,id)==0)
           return i;   
    }
    return -1;
}

// 添加学生关联(边)
void AddLink(Graph *g,char *id1,char *id2){
    int i1=FindStuIdx(g,id1);
    int i2=FindStuIdx(g,id2);
    if(i1==-1||i2==-1){
        printf("未查找到学生%s或学生%s，无法添加关联!\n",id1,id2);
        return ;
    }else{
        // 添加i1->i2的关联    
        Edge *e1=(Edge *)malloc(sizeof(Edge));
        e1->idx=i2;
        e1->next=g->stu[i1].link;
        g->stu[i1].link=e1;
        // 无向图要双向关联
        // 添加i2->i1的关联    
        Edge *e2=(Edge *)malloc(sizeof(Edge));
        e2->idx=i1;
        e2->next=g->stu[i2].link;
        g->stu[i2].link=e2;
        g->link_num++;
        printf("学生%s和学生%s添加关联成功!\n",id1,id2);
    }
}

// 删除学生关联(边)()
void DelLink(Graph *g,char *id1,char *id2){
    int i1=FindStuIdx(g,id1);
    int i2=FindStuIdx(g,id2);
    if(i1==-1||i2==-1){
        printf("未查找到学生%s或学生%s，无法删除关联!\n",id1,id2);
        return ;
    }
    int deleted=0;
    Edge *pre,*curr;
    pre=NULL,curr=g->stu[i1].link;
    while(curr&&curr->idx!=i2){
        pre=curr;
        curr=curr->next;
    }
    if(curr){
        pre?(pre->next=curr->next):(g->stu[i1].link=curr->next);  // 若pre不为空，则删除中间或末尾结点，否则删除第一个结点
        free(curr);
        deleted=1;
    }
    pre=NULL,curr=g->stu[i2].link;
    while(curr&&curr->idx!=i1){
        pre=curr;
        curr=curr->next;
    }
    if(curr){
        pre?(pre->next=curr->next):(g->stu[i2].link=curr->next);  
        free(curr);
        deleted=1;
    }
    if(deleted){
        g->link_num--;
        printf("学生%s和学生%s的关联边删除成功!\n",id1,id2);
    }else{
        printf("未找到学生%s和学生%s的关联，无需删除关联边!\n",id1,id2);
    }
}    

// 打印学生信息()
void ShowStu(Student s){
    printf("学号:%s 姓名:%s 成绩:%.1f\n",s.id,s.name,s.score);
}

// 查找单个学生()
void FindOneStu(Graph *g,char *id){
    int i=FindStuIdx(g,id);
    if(i!=-1){
        ShowStu(g->stu[i]);
    }else{
        printf("未查找到学生%s!\n",id);
    }
}

//修改成绩
void ChangeScore(Graph *g,char *id,float new_sc){
    int i=FindStuIdx(g,id);
    if(i!=-1){
        g->stu[i].score=new_sc;
        printf("学生%s成绩修改成功!\n",id);
    }else{
        printf("未查找到学生%s!无法修改成绩!\n",id);
    }
}

// 删除学生
void DelStu(Graph *g, char *id) {
    int idx = FindStuIdx(g, id);
    if (idx == -1) {
        printf("未找到学生%s，无法删除!\n", id);
        return;
    }

    // 删除所有邻接顶点中与该学生的关联
    Edge *p = g->stu[idx].link;
    while (p) {
        int adjIdx = p->idx;
        Edge *pre = NULL, *curr = g->stu[adjIdx].link;
        // 在邻接顶点的链表中删除与目标顶点的边
        while (curr && curr->idx != idx) {
            pre = curr;
            curr = curr->next;
        }
        if (curr) {
            if (pre) {
                pre->next = curr->next;
            } else {
                g->stu[adjIdx].link = curr->next;
            }
            free(curr);
        }
        p = p->next;
    }

    // 释放目标学生的邻接链表
    Edge *delP = g->stu[idx].link;
    while (delP) {
        Edge *temp = delP;
        delP = delP->next;
        free(temp);
    }
    g->stu[idx].link = NULL;

    // 顶点数组移位
    for (int i = idx; i < g->stu_num - 1; i++) {
        g->stu[i] = g->stu[i + 1];
        // 修正移位后邻接节点的下标（若邻接节点在当前节点之后，下标需减1）
        Edge *adjP = g->stu[i].link;
        while (adjP) {
            if (adjP->idx > idx) {
                adjP->idx--;
            }
            adjP = adjP->next;
        }
    }
    g->stu_num--;
    printf("学生%s已成功删除!\n", id);
}

//统计成绩
void StatScore(Graph *g){
    if(g->stu_num==0){
        printf("没有学生，无法统计成绩!\n");
        return ;
    }
    float avg,max,min;
    avg=0;
    max=g->stu[0].score;
    min=g->stu[0].score;
    for(int i=0;i<g->stu_num;i++){
        avg+=g->stu[i].score;
        max=(g->stu[i].score>max?g->stu[i].score:max);
        min=(g->stu[i].score<min?g->stu[i].score:min);
    }
    avg/=g->stu_num;
    printf("平均分:%.1f | 最高分:%.1f | 最低分:%.1f\n",avg,max,min);
}

// 成绩排序
void SortScore(Graph *g){
    if(g->stu_num==0){
        printf("没有学生，无法根据成绩排序!\n");
        return ;
    }
    InsertSort(g);
    for(int i=0;i<g->stu_num;i++){
        ShowStu(g->stu[i]);
    }
}

// 直接插入排序
void InsertSort(Graph *g){
    int i,j;
    Student temp;
    for(i=0;i<g->stu_num-1;i++){
        temp=g->stu[i+1];
        j=i;
        // 成绩大的在前，成绩相等时，学号小的在前
        while(j>-1&&(temp.score>g->stu[j].score||(temp.score==g->stu[j].score&&strcmp(temp.id,g->stu[j].id)<0))){
            g->stu[j+1]=g->stu[j];
            j--;
        }
        g->stu[j+1]=temp;
    }
}

// 广度优先遍历
void BroadFirstTraverse(Graph *g, char *startId) {
    int idx = FindStuIdx(g, startId);
    if (idx == -1) {
        printf("未找到起始学生，无法遍历!\n");
        return;
    }

    for (int i = 0; i < g->stu_num; i++) {
        g->stu[i].visited = 0;
    }

    int queue[MAX_STU], front = 0, rear = 0;
    queue[rear++] = idx;
    g->stu[idx].visited = 1;

    printf("===== 从学号%s开始广度优先遍历 =====\n", startId);
    while (front < rear) {
        int v = queue[front++];
        ShowStu(g->stu[v]); 
        Edge *p = g->stu[v].link;
        while (p) {
            int w = p->idx;
            if (!g->stu[w].visited) {
                g->stu[w].visited = 1;
                queue[rear++] = w;
            }
            p = p->next;
        }
    }
    printf("遍历完成!\n");
}

// 1. 添加学生
void addStudent(Graph *g) {
    char id[ID_LEN], name[NAME_LEN];
    float score;
    printf("输入学号：");
    scanf("%s", id);
    printf("输入姓名：");
    scanf("%s", name);
    printf("输入成绩：");
    scanf("%f", &score);
    AddStu(g, id, name, score);
}

// 2. 添加学生关联
void addLink(Graph *g) {
    char id1[ID_LEN], id2[ID_LEN];
    printf("输入学生1学号：");
    scanf("%s", id1);
    printf("输入学生2学号：");
    scanf("%s", id2);
    AddLink(g, id1, id2);
}

// 3. 删除学生关联
void delLink(Graph *g) {
    char id1[ID_LEN], id2[ID_LEN];
    printf("输入学生1学号：");
    scanf("%s", id1);
    printf("输入学生2学号：");
    scanf("%s", id2);
    DelLink(g, id1, id2);
}


// 4. 查询单个学生
void queryOneStu(Graph *g) {
    char id[ID_LEN];
    printf("输入要查询的学生学号：");
    scanf("%s", id);
    FindOneStu(g, id);
}

// 5. 修改成绩
void modifyScore(Graph *g) {
    char id[ID_LEN];
    float newSc;
    printf("输入要修改的学生学号：");
    scanf("%s", id);
    printf("输入新成绩：");
    scanf("%f", &newSc);
    ChangeScore(g, id, newSc);
}

// 6. 删除学生
void delStudent(Graph *g) {
    char id[ID_LEN];
    printf("输入要删除的学生学号：");
    scanf("%s", id);
    DelStu(g, id); 
}
// 7. 统计成绩
void statScore(Graph *g) {
    StatScore(g);
}

// 8. 成绩排序
void sortScore(Graph *g) {
    SortScore(g);
}

// 9.广度优先遍历
void VisitStuBFS(Graph *g) {
    char startId[ID_LEN];
    printf("请输入遍历起始学生的学号：");
    scanf("%s", startId);
    BroadFirstTraverse(g, startId);
}

void Menu() {
    printf("\n===== 学生成绩管理系统（图结构） =====\n");
    printf("1. 添加学生\n");
    printf("2. 添加学生关联\n");
    printf("3. 删除学生关联\n");
    printf("4. 查询单个学生\n");
    printf("5. 修改成绩\n");
    printf("6. 删除学生\n");
    printf("7. 统计成绩(平均分/最高分/最低分)\n");
    printf("8. 成绩排序\n");
    printf("9. 广度优先遍历\n");
    printf("10. 保存并退出\n");
    printf("======================================\n");
    printf("请输入选项：");
}

int main() {
    Graph g;
    InitGraph(&g);
    int option;
    
    while (1) {
        Menu();
        scanf("%d", &option);
        
        switch (option) {
            case 1:
                addStudent(&g);
                break;
            case 2:
                addLink(&g);
                break;
            case 3:
                delLink(&g);
                break;
            case 4:
                queryOneStu(&g);
                break;
            case 5:
                modifyScore(&g);
                break;
            case 6:
                delStudent(&g);
                break;
            case 7:
                statScore(&g);
                break;
            case 8:
                sortScore(&g);
                break;
            case 9:
                VisitStuBFS(&g);
                break;
            case 10:
                printf("系统已保存，即将退出...\n");
                return 0;
            default:
                printf("输入选项无效，请重新输入！\n");
        }
    }
    return 0;
}